/**
 * @file     mergeKlIsts.js
 * @brief    [23. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/)
 * @author   Zhu
 * @date     2022-03-17 21:36
 */

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    const k = lists.length;
    const heads = lists;
    const preHead = new ListNode();
    let pre = preHead;

    while (true) {
        let min = 0;
        while (min < k && !heads[min]) min++;
        if (min === k) break; // 全空
        for (let i = min + 1; i < k; i++) {
            if (!heads[i]) continue;
            if (heads[i].val < heads[min].val) {
                min = i;
            }
        }
        pre.next = heads[min];
        heads[min] = heads[min].next;
        pre = pre.next;
    }

    return preHead.next;
};

/**
 * 分治
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    function mergeTwoLists(l1, l2) {
        const vHead = new ListNode();
        let cur = vHead;
        while (l1 && l2) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return vHead.next;
    }

    // 分治
    function merge(lists, l, r) {
        if (l > r) return null;
        if (l == r) return lists[l];
        const mid = Math.floor((r + l) / 2);
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    return merge(lists, 0, lists.length - 1);
};
